package me.timlong;

public class LinkedNodeCopy {
    /**
     * 题目描述:
     * 现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。
     * 请对这个链表进行深拷贝。
     *
     * 解决方案：
     * 先对链表的各个节点进行复制，并将新创建的链表隔个添加进去
     *
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if(null == head)
            return null;

        RandomListNode pNode = head;
        RandomListNode tmpNode;
        //该层循环完成在每个节点后添加一个前一个节点的copy，random未定

        while(null != pNode){
            tmpNode = new RandomListNode(pNode.label);
            tmpNode.next = pNode.next;
            pNode = pNode.next = tmpNode;
            pNode = pNode.next;
        }

        // 复制copy节点的random
        pNode = head;
        while(null != pNode){
            tmpNode = pNode.next;
        // pNode.random.next 是PNodeRandom的一个拷贝
            tmpNode.random = (null != pNode.random ? pNode.random.next : null);
            pNode = tmpNode.next;
        }

        pNode = head;
        RandomListNode copyHead = head.next;
        // 分离两条链，保证原链表不变
        while(null != pNode){
            tmpNode = pNode.next;
            pNode.next = tmpNode.next;
            tmpNode.next = (null == tmpNode.next ? null : tmpNode.next.next);
            pNode = pNode.next;
        }
        return copyHead;
    }

    public static void main(String[] args) {
        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);

        node1.next = node2;
        node1.random = node3;
        node2.next = node3;
        node2.random = node1;
        node3.random = node3;

        RandomListNode copy = new LinkedNodeCopy().copyRandomList(node1);

        while(null != copy){
            System.out.println(copy.label + ", " + copy.random.label + "| ");
            copy = copy.next;

        }


    }

}


/**
 * Definition for singly-linked list with a random pointer.
 *
 */
class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
};
